package com.zh.note.leetcode.tree;

import com.zh.note.leetcode.model.TreeNode;

/**
 * 222. 完全二叉树的节点个数
 */
public class LC_222_countNodes {

    // public int countNodes(TreeNode root) {
    //     if (root == null) {
    //         return 0;
    //     }
    //     int leftNode = countNodes(root.left);
    //     int rightNode = countNodes(root.right);
    //     return leftNode + rightNode + 1;
    //
    // }

    public int countNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }
        // 开始根据左深度和右深度是否相同来判断该子树是不是满二叉树
        TreeNode left = root.left;
        TreeNode right = root.right;
        int leftDepth = 0;
        int rightDepth = 0;
        while (left != null) { // 求左子树深度
            left = left.left;
            leftDepth++;
        }
        while (right != null) {
            right = right.right;
            rightDepth++;
        }
        if (leftDepth == rightDepth) {
            return (2 << leftDepth) - 1; // 注意(2<<1) 相当于2^2，所以leftDepth初始为0
        }
        return countNodes(root.left) + countNodes(root.right) + 1;

    }
}
